package com.jay.structure.link;

import java.util.Scanner;

/**
 * Created by caoyuan7 on 2018/12/11.
 */
public class MergeSortList {
    public static void main(String args[]) {
        Node la, lb, lc;
        la = creat_list(5);
        lb = creat_list(4);
       // lc = la;
       // print_list(la);
        //print_list(lb);
        // merge_list(la, lb);
        print_list(merge_list(la, lb));
    }
    // 链表创建方法
    static Node creat_list(int n) {
        System.out.println("input "+n+" values:");
        Scanner scn = new Scanner(System.in);
        Node head = null;
        Node p;
        //head = new Node();
        //head.next = null;
        for (int i = 0; i < n; i++) {
            if(i==0){
                head =new Node();
                head.data=scn.nextInt();
                head.next=null;
                continue;
            }
            // while (t.next!=null) t=t.next;
            p = new Node();
            p.data = scn.nextInt();
            p.next=head;
            head = p;
        }
        return head;
    }

    static Node merge_list(Node la, Node lb) {
        Node pc=null,lc=null;
        int i=0;
        while ((la != null) && (lb != null)) {
            if(i==0) {
                if (la.data <= lb.data) {
                    pc = la;
                    la = la.next;
                } else {
                    pc = lb;
                    lb = lb.next;
                }
                lc=pc;
                i++;
                continue;
            }
            if (la.data <= lb.data) {
                pc.next = la;
                pc=la;
                la = la.next;
            } else {
                pc.next = lb;
                pc=lb;
                lb = lb.next;
            }

        }
        pc.next = (la==null)?lb:la;
        return lc;
    }
    // 链表打印输出方法
    static void print_list(Node head) {
        while (head != null) {
            System.out.println("[" + head.data + "]");
            head = head.next;
        }
    }
}
class Node {
    int data;
    Node next;
}